S.-T. Yau College Student Mathematics Contests 2022

Problem 1. Consider ${\{p_i(x)\}}_{i=0}^{\mathrm{\infty }}$${\left\{p_i(x)\right\}}_{i=0}^{\mathrm{\infty }}${p_(i)(x)}_(i=0)^(oo)\left\{p_{i}(x)\right\}_{i=0}^{\infty}${\{p_i(x)\}}_{i=0}^{\mathrm{\infty }}$, a family of orthogonal polynomials associated with the inner product

where $p_i(x)$$p_i(x)$p_(i)(x)p_{i}(x)$p_i(x)$ is a polynomial of degree $i$$i$ii$i$. Let $x_0,x_1,\dots ,x_n$$x_0,x_1,\dots ,x_n$x_(0),x_(1),dots,x_(n)x_{0}, x_{1}, \ldots, x_{n}$x_0,x_1,\dots ,x_n$ be the roots of $p_{n+1}(x)$$p_{n+1}(x)$p_(n+1)(x)p_{n+1}(x)$p_{n+1}(x)$. Construct an orthonormal basis in the subspace of the polynomials of degree no more than $n$$n$nn$n$ such that, for any polynomial in this subspace, the coefficients of its expansion into the basis are equal to the scaled values of this polynomial at the nodes $x_0,x_1,\dots ,x_n$$x_0,x_1,\dots ,x_n$x_(0),x_(1),dots,x_(n)x_{0}, x_{1}, \ldots, x_{n}$x_0,x_1,\dots ,x_n$.

Solution: Start by considering $l_i(x),i=0,\dots ,n$$l_i(x),i=0,\dots ,n$l_(i)(x),i=0,dots,nl_{i}(x), i=0, \ldots, n$l_i(x),i=0,\dots ,n$, the Lagrange interpolating polynomials of degree $n$$n$nn$n$ for the nodes $x_0,x_1,\dots ,x_n$$x_0,x_1,\dots ,x_n$x_(0),x_(1),dots,x_(n)x_{0}, x_{1}, \ldots, x_{n}$x_0,x_1,\dots ,x_n$. Let us compute the inner product of two such polynomials using the Gaussian quadrature, exact for the polynomials of degree less or equal to $2n+1$$2n+1$2n+12 n+1$2n+1$. We have

where $w_0,w_1,\dots ,w_n$$w_0,w_1,\dots ,w_n$w_(0),w_(1),dots,w_(n)w_{0}, w_{1}, \ldots, w_{n}$w_0,w_1,\dots ,w_n$ are the positive weights of the quadrature.

We now normalize the Lagrange interpolating polynomials,

and obtain

namely, these functions form an orthonormal basis. The coefficients of a function in this subspace are computed as projections on the basis,

Problem 2. Consider a 2D fixed point iteration of the form

Assume that the vector-valued function $\overrightarrow{H}(x,y)=(f(x,y),g(x,y){)}^T$$\overrightarrow{H}(x,y)=(f(x,y),g(x,y){)}^T$vec(H)(x,y)=(f(x,y),g(x,y))^(T)\vec{H}(x, y)=(f(x, y), g(x, y))^{T}$\overrightarrow{H}(x,y)=(f(x,y),g(x,y){)}^T$ is continuously-differentiable, and the infinity norm of the Jacobian matrix is less than 1 at a unique fixed point $(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$$\left(x_{\mathrm{\infty }},y_{\mathrm{\infty }}\right)$(x_(oo),y_(oo))\left(x_{\infty}, y_{\infty}\right)$(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$.

Now consider a new iteration:

Prove that iteration (2) is convergent, to the same fixed point as iteration (1), for the initial conditions sufficiently close to the fixed point.

Solution: First, we check that the new iteration has the same fixed point as the original iteration. For (1), $x_{\mathrm{\infty }}=f(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$$x_{\mathrm{\infty }}=f\left(x_{\mathrm{\infty }},y_{\mathrm{\infty }}\right)$x_(oo)=f(x_(oo),y_(oo))x_{\infty}=f\left(x_{\infty}, y_{\infty}\right)$x_{\mathrm{\infty }}=f(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$, $y_{\mathrm{\infty }}=g(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$$y_{\mathrm{\infty }}=g\left(x_{\mathrm{\infty }},y_{\mathrm{\infty }}\right)$y_(oo)=g(x_(oo),y_(oo))y_{\infty}=g\left(x_{\infty}, y_{\infty}\right)$y_{\mathrm{\infty }}=g(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$. Thus, we have for the new iteration,

Next, the Jacobian of the new iteration reads as

The infinity norm of the Jacobian is the maximum absolute row sum. The first row has exactly the same absolute row sum as the Jacobian of the original iteration, thus we have

The absolute row sum for the second row is

Evaluating at $(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$$\left(x_{\mathrm{\infty }},y_{\mathrm{\infty }}\right)$(x_(oo),y_(oo))\left(x_{\infty}, y_{\infty}\right)$(x_{\mathrm{\infty }},y_{\mathrm{\infty }})$, we have

Thus, the Jacobian of the new iteration has infinity norm less than 1 at the fixed point. Since the new iteration is continuouslydifferentiable, there must be a neighborhood of the fixed point such that iterations initialized in this neighborhood will converge.

Problem 3. Let $A\in {\mathbf{R}}^{\mathbf{m}\times \mathbf{m}}$$A\in {\mathbf{R}}^{\mathbf{m}\times \mathbf{m}}$A inR^(mxxm)A \in \mathbf{R}^{\mathbf{m} \times \mathbf{m}}$A\in {\mathbf{R}}^{\mathbf{m}\times \mathbf{m}}$ be a matrix with entries $a_{ij}$$a_{ij}$a_(ij)a_{i j}$a_{ij}$ which satisfy

(a) Prove that $A^{-1}$$A^{-1}$A^(-1)A^{-1}$A^{-1}$ exists.

(b) Prove that $\parallel A{\parallel }_{\mathrm{\infty }}$$\parallel A{\parallel }_{\mathrm{\infty }}$||A||_(oo)\|A\|_{\infty}$\parallel A{\parallel }_{\mathrm{\infty }}$ is the max row sum (of absolute values) of $A$$A$AA$A$.

(c) Find both a lower and upper bound for $\parallel A{\parallel }_{\mathrm{\infty }}$$\parallel A{\parallel }_{\mathrm{\infty }}$||A||_(oo)\|A\|_{\infty}$\parallel A{\parallel }_{\mathrm{\infty }}$.

(d) Now assume $A=A^T$$A=A^T$A=A^(T)A=A^{T}$A=A^T$. Find bounds for $\parallel A{\parallel }_2$$\parallel A{\parallel }_2$||A||_(2)\|A\|_{2}$\parallel A{\parallel }_2$ and ${\parallel A^{-1}\parallel }_2$${∥A^{-1}∥}_2$||A^(-1)||_(2)\left\|A^{-1}\right\|_{2}${\parallel A^{-1}\parallel }_2$.

(a) Suppose $A$$A$AA$A$ is singular and $v={\left[\begin{array}{llll}{v}_1& v_2& \cdots & v_m\end{array}\right]}^T$$v={\left[\begin{array}{l}{v}_1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}{v}_2\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\cdots \hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}{v}_m\end{array}\right]}^T$v=[[v_(1),v_(2),cdots,v_(m)]]^(T)v=\left[\begin{array}{llll}v_{1} & v_{2} & \cdots & v_{m}\end{array}\right]^{T}$v={\left[\begin{array}{llll}{v}_1& v_2& \cdots & v_m\end{array}\right]}^T$ be an eigenvector corresponding to eigenvalue 0 with $\underset{j}{max}\left|v_j\right|=\left|v_k\right|$$\underset{j}{max} \left|v_j\right|=\left|v_k\right|$max_(j)|v_(j)|=|v_(k)|\max _{j}\left|v_{j}\right|=\left|v_{k}\right|$\underset{j}{max}\left|v_j\right|=\left|v_k\right|$. Consider the $k$$k$kk$k$-th row of the vector equation $Av=0$$Av=0$Av=0A v=0$Av=0$,

Therefore,

which is a contradiction.
(b) Suppose the $k$$k$kk$k$-th row has the max absolute sum, i.e.,

For the vector $v$$v$vv$v$ with $v_j=\mathrm{sgn}\left(a_{kj}\right)$$v_j=\mathrm{sgn}\left(a_{kj}\right)$v_(j)=sgn(a_(kj))v_{j}=\operatorname{sgn}\left(a_{k j}\right)$v_j=\mathrm{sgn}\left(a_{kj}\right)$, we have

since the right hand side is the $k$$k$kk$k$-th element of $Av$$Av$AvA v$Av$. Noting that $\parallel v{\parallel }_{\mathrm{\infty }}=1$$\parallel v{\parallel }_{\mathrm{\infty }}=1$||v||_(oo)=1\|v\|_{\infty}=1$\parallel v{\parallel }_{\mathrm{\infty }}=1$, we have $\parallel A{\parallel }_{\mathrm{\infty }}\ge \sum _j\left|a_{kj}\right|$$\parallel A{\parallel }_{\mathrm{\infty }}\ge \sum _j \left|a_{kj}\right|$||A||_(oo) >= sum_(j)|a_(kj)|\|A\|_{\infty} \geq \sum_{j}\left|a_{k j}\right|$\parallel A{\parallel }_{\mathrm{\infty }}\ge \sum _j\left|a_{kj}\right|$. For the other inequality, we have that for any vector $u$$u$uu$u$,

(c) From given information,

Therefore, $2\le \parallel A{\parallel }_{\mathrm{\infty }}\le 12$$2\le \parallel A{\parallel }_{\mathrm{\infty }}\le 12$2 <= ||A||_(oo) <= 122 \leq\|A\|_{\infty} \leq 12$2\le \parallel A{\parallel }_{\mathrm{\infty }}\le 12$.

(d) $A=A^T$$A=A^T$A=A^(T)A=A^{T}$A=A^T$ means singular values are the absolute values of (real) eigenvalues. By the Gershgorin Theorem,

Therefore,

By given info.

Now since $A=A^T$$A=A^T$A=A^(T)A=A^{T}$A=A^T$ and $A$$A$AA$A$ is invertible, the smallest and largest singular values of $A^{-1}$$A^{-1}$A^(-1)A^{-1}$A^{-1}$ will be the reciprocal of the largest and smallest singular values of $A$$A$AA$A$ respectively. Hence,

Problem 4. Consider a system of ODE initial value problems of the form:

Assume that $f(u)$$f(u)$f(u)f(u)$f(u)$ has the property that the forward Euler (FE) method:

satisfies

for some norm $\parallel \cdot \parallel$$\parallel \cdot \parallel$||*||\|\cdot\|$\parallel \cdot \parallel$ and for all time-steps $k,0<k\le k_{FE}$$k,0<k\le k_{FE}$k,0 < k <= k_(FE)k, 0<k \leq k_{F E}$k,0<k\le k_{FE}$. Now consider the 2-stage Runge-Kutta method:

where

(a) Prove that the above 2-stage Runge-Kutta method also satisfies the inequality:

under some appropriate time-step restriction: $0\le k\le k^{\ast }$$0\le k\le k^{\ast }$0 <= k <= k^(**)0 \leq k \leq k^{*}$0\le k\le k^{\ast }$, where you need to explicitly determine $k^{\ast }$$k^{\ast }$k^(**)k^{*}$k^{\ast }$ in terms of $k_{FE}$$k_{FE}$k_(FE)k_{F E}$k_{FE}$.

(b) Explicitly determine the coefficients:

so that

(i) The method is second-order accurate; and

(ii) The maximum allowed time-step, $k^{\ast }$$k^{\ast }$k^(**)k^{*}$k^{\ast }$, is as large as possible.

(a) The first stage is simply the forward Euler method with a time step $k{\beta }_{10}$$k{\beta }_{10}$kbeta_(10)k \beta_{10}$k{\beta }_{10}$. Therefore, as long as

we have that

The second stage can be written as a linear combination of two forward Euler steps:

Requiring that

we get that

Therefore, the 2-stage RK method satisfies $\parallel U^{(1)}\parallel \le \parallel U^n\parallel$$∥U^{(1)}∥\le ∥U^n∥$||U^((1))|| <= ||U^(n)||\left\|U^{(1)}\right\| \leq\left\|U^{n}\right\|$\parallel U^{(1)}\parallel \le \parallel U^n\parallel$ under the following time-step constraint: